/* vim: ft=c */
#ifndef GNOME_SORT_INCLUDED
#define GNOME_SORT_INCLUDED
/******************************************************************************
* (c)2025 Michael T. Richter
*
* This software is distributed under the terms of WTFPLv2.  The full terms and
* text of the license can be found at http://www.wtfpl.net/txt/copying
******************************************************************************/

/** @file
 *  @brief Implementation of the Gnome sort for integers and generic types.
 *
 *  Gnome sorts are grossly inefficient at scale, but if you have a small
 *  number of items to sort and need to do it in a small amount of code space
 *  (like would be the case in most bare-metal embedded systems), they are a
 *  god-send.
 *
 *  This library implements two kinds of Gnome sorts: specialized for the most
 *  common case (integers), and customizable by data type.
 */
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>

/**** CONFIGURATION - user-adjustable parameters go here *********************/
/* Note: -DDEFAULT_GSORT_TYPE=<type> in the command line works too.          */
#ifdef DEFAULT_GSORT_TYPE
typedef DEFAULT_GSORT_TYPE gsort_t;
#else
typedef int32_t gsort_t;
#endif
/*****************************************************************************/

/*! Function pointer type for custom "greater than" comparisons of user types. */
typedef bool (*gsort_gt_t)(const void *, const void *);
/*! Function pointer type for custom value swaps of user types. */
typedef void (*gsort_swap_t)(void *, void *);

/*! Sort an array of integers (gsort_t) in-place with a gnome sort.
 *
 *  @param[in,out]  array      The array to sort.
 *  @param[in]      array_size The number of **elements** in the array.
 */
void gnome_sort_i(gsort_t array[], size_t array_size);

/*! Sort an array of arbitrary type in-place with a gnome sort.
 *
 *  @param[in,out]  array      The array to sort.
 *  @param[in]      array_size The number of **elements** in the array.
 *  @param[in]      elem_size  The number of bytes each element takes up.
 *  @param[in]      gt_op      Function pointer: returns true if first operand is greater.
 *  @param[in]      swap_op    Function pointer: swaps its operands in place.
 */
void gnome_sort(void *array, size_t array_size, size_t elem_size, gsort_gt_t gt, gsort_swap_t swap);

static inline void gnome_sort_p(void *array, size_t array_size, gsort_gt_t gt, gsort_swap_t swap)
{
    gnome_sort(array, array_size, sizeof(void *), gt, swap);
}

#ifdef GNOME_SORT_IMPLEMENTATION
/*******************************************************************************
* GNOME_SORT IMPLEMENTATION SECTION
* =================================
*
* In a single source file in your project, the symbol GNOME_SORT_IMPLEMENTATION
* must be defined before including the header:
*
*   ```c
*   #define GNOME_SORT_IMPLEMENTATION
*   #include "gnome_sort.h"
*   ```
*
* All other source files using this library must *not* define this symbol.
*******************************************************************************/
#include <stdbool.h>

#ifdef DEBUG
#include <stdio.h>
#define DEBUG_OUT(F, ...) fprintf(stderr, F, __VA_ARGS__)
#else
#define DEBUG_OUT(F, ...)
#endif

static inline void gs_static_swap_i(gsort_t array[], size_t i, size_t j)
{
    gsort_t t = array[i];
    array[i] = array[j];
    array[j] = t;
}
static inline bool gs_static_gt_i(gsort_t i, gsort_t j)
{
    return i > j;
}
void gnome_sort_i(gsort_t array[], size_t array_size)
{
    if (array_size < 2) return;
    for (size_t i = 1, j = 2 ; i < array_size ;)
    {
        if (gs_static_gt_i(array[i - 1], array[i]))
        {
            gs_static_swap_i(array, i - 1, i);

            if (--i > 0)
            {
                continue;
            }
        }

        i = j++;
    }
}

void gnome_sort(void *array, size_t array_size, size_t elem_size, gsort_gt_t gt, gsort_swap_t swap)
{
    if (array_size < 2) return;

    uint8_t *base = array;
    for (size_t i = 1, j = 2 ; i < array_size ;)
    {
        void *prev = (void *)(base + ((i - 1) * elem_size));
        void *curr = (void *)(base + (i       * elem_size));
        if (gt(prev, curr))
        {
            swap(prev, curr);
            if (--i > 0)
            {
                continue;
            }
        }
        i = j++;
    }
}
#endif //GNOME_SORT_IMPLEMENTATION

#endif //GNOME_SORT_INCLUDED
